﻿open System

type 'a MyList =
    | Empty
    | List of 'a * 'a MyList
    
    member this.FilterUnordered filter =
        let rec filter_tail list result =
            match list with
            | Empty -> result
            | List(head, tail) ->
                if filter head then
                    filter_tail tail (List(head, result))
                else
                    filter_tail tail result
        
        filter_tail this Empty
    
    member this.Filter filter =
        let rec filter_tail list result =
            match list with
            | Empty -> result
            | List(head, tail) ->
                if filter head then
                    filter_tail tail (List(head, result))
                else
                    filter_tail tail result
        
        (filter_tail this Empty).Reversed
    
    member this.ForEach func =
        match this with
        | Empty -> ()
        | List(head, tail) ->
            func head
            tail.ForEach func
    
    member private this.RConcat other =
        let rec rconcat_tail list result =
            match list with
            | Empty -> result
            | List(head, tail) ->
                rconcat_tail tail (List(head, result))
        
        rconcat_tail this other
    
    member this.Reversed =
        this.RConcat Empty
    
    member this.Concat other =
        this.Reversed.RConcat other
    
    member this.Reduce func =
        let rec reduce_tail state rest =
            match rest with
            | Empty -> state
            | List(head, tail) ->
                reduce_tail (func state head) tail
        
        match this with
        | Empty -> InvalidOperationException() |> raise
        | List(head, tail) ->
            reduce_tail head tail
    
    [<OverloadID("append_list")>]
    static member (+) ((left: 'a MyList), right) =
        left.Concat right
    
    [<OverloadID("append_item")>]
    static member (+) (item, list) =
        List(item, list)
    
    static member New(list)=
        let rec rconcat_tail list result =
            match list with
            | [] -> result
            | head :: tail ->
                rconcat_tail tail (List(head, result))
        
        let result = rconcat_tail list Empty
        result.Reversed

let rec qsort (input: 'a list when 'a:> IComparable<'a> and 'a : struct) =
//let rec qsort (input: int list) =
    match input with
    | median :: rest ->
        let left = rest |> List.filter (fun it -> it.CompareTo(median)<0) |> qsort
        let right = rest |> List.filter (fun it -> it.CompareTo(median)>=0) |> qsort
        left @ median :: right
    | [] -> []

let rec myqsort (list: 'a MyList) =
    match list with
    | Empty -> Empty
    | List(head, tail) ->
        let left = tail.Filter (fun it -> it < head)
        let right = tail.Filter (fun it-> it >= head)
        (myqsort left).Concat(List(head, myqsort right))

let random = Random()

let rlist length =
    let rec rlist_tail accum = function
        | 0u -> accum
        | length ->
            rlist_tail (random.Next() :: accum) (length - 1u)
    
    rlist_tail [] length

let myrlist length =
    let rec rlist_tail (accum: int MyList) = function
        | 0u -> accum
        | length ->
            rlist_tail (random.Next() + accum) (length - 1u)
    
    rlist_tail MyList.Empty length

let myrlistf length =
    let rec rlist_tail (accum: float MyList) = function
        | 0u -> accum
        | length ->
            rlist_tail (random.NextDouble() + accum) (length - 1u)
    
    rlist_tail MyList.Empty length

let measure action =
    let start = DateTime.Now
    do action()
    DateTime.Now - start

for i in 10 .. 20 do
    let length = (1u <<< i)
    let input = rlist length
    let action()=
        qsort input
        |> List.reduce (fun a b -> a + b)
        |> Console.WriteLine
    
    let best()=
        List.sort input
        |> List.reduce (fun a b -> a + b)
        |> Console.WriteLine
    
    let time = measure action
    let btime = measure best
    
    printfn "%u:\t%A\t%A" i time.TotalSeconds btime.TotalSeconds

Console.WriteLine()

let test =
    rlist 100u
    |> MyList<_>.New
    |> myqsort



test.ForEach Console.WriteLine
